/**
 * 538. 把二叉搜索树转换为累加树（与 1038 同）
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 */
public class Solutions_538 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(5);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(13);  // output: {18, 20, 13}

        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);
        // output: {30, 36, 31, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8}

        TreeNode result = convertBST(root);
        System.out.println(result);
    }


    public static TreeNode convertBST(TreeNode root) {
        // 中序遍历（右中左顺序）
        convertBST_dfs(root, 0);
        return root;
    }

    public static int convertBST_dfs(TreeNode root, int sumVal) {
        if (root == null) {
            return sumVal;
        }
        if (root.left == null && root.right == null) {
            // 为叶子节点时，计算结果并返回
            root.val += sumVal;
            return root.val;
        }
        // 对于右子树节点，比它大的数值只能是其右子树的节点
        int rightRes = convertBST_dfs(root.right, sumVal);
        // 对于根节点，比它大的数值只能是其右子树下的节点
        root.val += rightRes;
        // 对于左子树节点，比它大的数值有根节点及右子树下的节点
        int leftRes = convertBST_dfs(root.left, root.val);
        return leftRes;
    }
}
